#include "DynamicArray.h"
#include <iostream>
#include <cmath>

namespace DARRAY
{
    // 构造
    DynamicArray::DynamicArray() : size(0), capacity(10)
    {
        array = new ElementType[capacity];
        Free = nullptr;
        print = nullptr;
        compare = nullptr;
    }

    // 拷贝
    DynamicArray::DynamicArray(const DynamicArray &a)
    {
        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];
        for (size_t i = 0; i < size; i++)
        {
            array[i] = a.array[i];
        }
    }

    // 运算符重载
    DynamicArray &DynamicArray::operator=(const DynamicArray &a)
    {
        delete[] array;
        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];
        for (size_t i = 0; i < size; i++)
        {
            array[i] = a.array[i];
        }
        return *this;
    }

    // 析构
    DynamicArray::~DynamicArray()
    {
        if (Free)
        {
            for (size_t i = 0; i < size; i++)
            {
                Free(array[i]);
            }
        }
        delete[] array;
    }

    // 尾插法
    void DynamicArray::InsertTail(const ElementType &element) // 不扩容：O(1) 扩容：O(n)
    {
        if (size == capacity) // 数组满的时候
        {
            ReSize(capacity * 2);
        }
        array[size++] = element;
    }

    // 头插法
    void DynamicArray::InsertHead(const ElementType &element) // 扩容/不扩容 O(n)
    {
        if (size == capacity) // 数组满的时候
        {
            ReSize(capacity * 2);
        }
        for (size_t i = size; i > 0; i--)
        {
            array[i] = array[i - 1];
        }
        array[0] = element;
        size++;
    }

    // 通过下标插入
    void DynamicArray::InsertByIndex(const ElementType &element, size_t index)
    {
        if (index > size)
        {
            std::cout << "插入位置非法！\n";
            return;
        }
        if (size == capacity) // 数组满的时候
        {
            ReSize(capacity * 2);
        }
        for (size_t i = size; i > index; i--)
        {
            array[i] = array[i - 1];
        }
        array[index] = element;
        size++;
    }

    // 通过下标移除
    void DynamicArray::RemoveByIndex(size_t index) // o(n)
    {
        if (index >= size)
        {
            std::cout << "删除位置非法!\n";
            return;
        }
        for (size_t i = index; i < size - 1; i++)
        {
            array[i] = array[i + 1];
        }
        size--;
    }

    // 通过数组移除
    void DynamicArray::RemoveByElement(const ElementType &element) // O(n^2)
    {
        for (size_t i = 0; i < size; i++)
        {
            if (AllCompare(array[i], element))
            {
                RemoveByIndex(i);
                i--;
            }
        }
    }

    ElementType *DynamicArray::FindByIndex(size_t index) // O(1)
    {
        if (index >= size)
        {
            return nullptr;
        }
        return &array[index]; // 因为地址连续，所以查找速度很快
    }

    DynamicArray DynamicArray::FindByElement(const ElementType &element) // O(n)
    {
        DynamicArray result;
        for (size_t i = 0; i < size; i++)
        {
            if (AllCompare(array[i], element))
            {
                result.InsertTail((void *)i);
            }
        }
        return result;
    }

    void DynamicArray::UpdateByIndex(size_t index, const ElementType &newValue) // O(1)
    {
        if (index >= size)
        {
            std::cout << "位置非法" << std::endl;
            return;
        }
        array[index] = newValue;
    }

    void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue) // O(n)
    {
        for (size_t i = 0; i < size; i++)
        {
            if (AllCompare(array[i], oldValue))
            {
                array[i] = newValue;
            }
        }
    }

    ElementType &DynamicArray::operator[](int index)
    {
        return array[index];
    }

    void DynamicArray::Sort()
    {
        FastSort(0, size - 1, 0, 2 * log2(size));
    }

    void DynamicArray::Duplicate() // O(n)
    {
        for (size_t i = 1; i < size; i++)
        {
            if (AllCompare(array[i], array[i - 1]))
            {
                RemoveByIndex(i);
                i--;
            }
        }
    }

    DynamicArray DynamicArray::Merge(const DynamicArray &a)
    {
        DynamicArray result;
        size_t first = 0;  // 当前数组
        size_t second = 0; // 传进来的数组

        while (first < this->size && second < a.size) // 两个数组都没有走到末尾
        {
            if (compare(array[first], a.array[second]) < 0)
                result.InsertTail(array[first++]);
            else
                result.InsertTail(a.array[second++]);
        }
        while (first < this->size)
            result.InsertTail(array[first++]);
        while (second < a.size)
            result.InsertTail(a.array[second++]);
        return result;
    }

    DynamicArray DynamicArray::FdIntrSctn(const DynamicArray &a) // O(n)
    {
        DynamicArray result;
        size_t first = 0;
        size_t second = 0;
        while (first < this->size && second < a.size)
        {
            if (AllCompare(array[first], a.array[second]))
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if (compare(array[first], a.array[second]) < 0)
            {
                first++;
            }
            else if (compare(array[first], a.array[second]) > 0)
            {
                second++;
            }
        }
        return result;
    }

    DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a)
    {
        DynamicArray result;
        size_t first = 0;
        size_t second = 0;
        while (first < this->size && second < a.size)
        {
            if (compare(array[first], a.array[second]) == 0)
            {
                result.InsertTail(array[first++]);
                second++;
            }
            else if (compare(array[first], a.array[second]) < 0)
            {
                result.InsertTail(array[first++]);
            }
            else if (compare(array[first], a.array[second]) > 0)
            {
                result.InsertTail(a.array[second++]);
            }
        }
        while (first < this->size)
            result.InsertTail(array[first++]);
        while (second < a.size)
            result.InsertTail(a.array[second++]);
        return result;
    }

    DynamicArray DynamicArray::FindDifference(const DynamicArray &a) // 相等往前走，谁小要谁()
    {
        DynamicArray result;
        size_t first = 0;
        size_t second = 0;
        while (first < this->size && second < a.size)
        {
            if (AllCompare(array[first], a.array[second]))
            {
                first++;
                second++;
            }
            else if (compare(array[first], a.array[second]) < 0)
            {
                result.InsertTail(array[first++]);
            }
            else if (compare(array[first], a.array[second]) > 0)
            {
                result.InsertTail(a.array[second++]);
            }
        }
        while (first < this->size)
            result.InsertTail(array[first++]);
        while (second < a.size)
            result.InsertTail(a.array[second++]);
        return result;
    }

    bool DynamicArray::operator==(const DynamicArray &a) // O(n)
    {
        if (size != a.size)
        {
            return false;
        }
        size_t first = 0;
        size_t second = 0;
        while (first < this->size && second < a.size)
        {
            if (compare(array[first++], a.array[second++]) != 0)
            {
                return false;
            }
        }
        return true;
    }

    size_t DynamicArray::BinarySearch(const ElementType &element)
    {
        size_t left = 0;
        size_t right = size - 1;
        while (left <= right)
        {
            size_t mid = left + (right - left) / 2;
            if (compare(array[mid], element) == 0)
            {
                return mid;
            }
            else if (compare(array[mid], element) > 0)
            {
                if (mid == 0)
                    return ULLONG_MAX;
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return ULLONG_MAX;
    }

    bool DynamicArray::Contains(const DynamicArray &a)
    {
        // DynamicArray s = FdIntrSctn(a);   // O(2n)
        // return s == a;
        size_t j = 0;
        for (size_t i = 0; i < size; i++)
        {
            if (compare(array[i], a.array[j]) == 0) // 依次找
                j++;
        }
        return j == a.size;
    }

    bool DynamicArray::ContnsContains(const DynamicArray &a)
    {
        for (size_t i = 0; i <= size - a.size; i++)
        {
            if (SubSquence(i, a.size) == a)
            {
                return true;
            }
        }
        return false;
    }

    DynamicArray DynamicArray::SubSquence(size_t index, size_t len)
    {
        DynamicArray result;
        if (index + len > size)
        {
            return result;
        }
        for (size_t i = 0; i < len; i++)
        {
            result.InsertTail((void *)(index + i));
        }
        return result;
    }

    size_t DynamicArray::partition(size_t start, size_t end)
    {
        size_t left = start;
        size_t right = end;
        ElementType temp = array[start];
        while (left < right)
        {
            while (compare(array[right], temp) > 0 && left < right)
            {
                right--;
            }
            if (left < right)
            {
                array[left++] = array[right];
            }
            while (compare(array[left], temp) < 0 && left < right)
            {
                left++;
            }
            if (left < right)
            {
                array[right--] = array[left];
            }
        }
        array[left] = temp;
        return left;
    }

    void DynamicArray::FastSort(size_t start, size_t end, size_t CurDepth, size_t MaxDepth)
    {
        if (start >= end)
            return;

        // 如果没有达到最大的递归深度
        if (CurDepth < MaxDepth)
        {
            size_t par = partition(start, end); // 对数列分组
            if (par != 0)
                FastSort(start, par - 1, CurDepth + 1, MaxDepth);
            FastSort(par + 1, end, CurDepth + 1, MaxDepth);
        }
        // 超过最大深度,选用其他排序算法
        else
        {
            InsertSort(start, end);
        }
    }

    void DynamicArray::InsertSort(size_t start, size_t end)
    {
        for (size_t i = start + 1; i <= end; i++)
        {
            size_t j = i;
            ElementType temp = array[i];
            for (; j > start; j--)
            {
                if (compare(array[j - 1], temp) > 0)
                    array[j] = array[j - 1];
                else
                {
                    break;
                }
            }
            array[j] = temp;
        }
    }

    void DynamicArray::ReSize(size_t capacity) //  重定义大小的函数
    {
        this->capacity = capacity;
        this->size = size > capacity ? capacity : size;
        ElementType *newPtr = new ElementType[capacity];
        for (size_t i = 0; i < size; i++)
        {
            newPtr[i] = array[i];
        }
        delete[] array;
        array = newPtr;
    }

    void DynamicArray::show()
    {
        for (size_t i = 0; i < size; i++)
        {
            print(array[i]);
        }
        // std::cout << size << std::endl;
    }
}
